package com.mybatis.audition;

import com.alibaba.fastjson.JSONObject;

/**
 * @author liuxiaoding
 * @Date 2022/3/3
 **/
public class HeapSort {
    public static void main(String[] args) {
        int[] arr=new int[]{1,8,-10,3,22,11,33,-22,88};
        sort(arr);
        System.out.println(JSONObject.toJSONString(arr));
    }

    /**
     * @param a
     */
    public static void sort(int[] a) {
         if(null==a||a.length==0){
             return;
         }
         int len=a.length;
         buildMaxHeap(a,len);
         for(int i=len-1;i>0;i--){
             swap(a,0,i);
             len--;
             heap(a,0,len);
         }

    }

    public static void buildMaxHeap(int[] arr,int len){
        for(int i=(int)Math.floor(len/2)-1;i>=0;i--){
            heap(arr,i,len);
        }
    }

    public static void heap(int[] arr,int i,int len){
        int left=2*i+1;
        int right=2*i+2;
        int bigIndex=i;
        if(left<len&&arr[left]>arr[bigIndex]){
            bigIndex=left;
        }
        if (right < len && arr[right] > arr[bigIndex]) {
            bigIndex=right;
        }
        if(bigIndex!=i){
            swap(arr,i,bigIndex);
            heap(arr,bigIndex,len);
        }
    }
    public static void swap(int[] arr,int i,int index){
        int temp=arr[index];
        arr[index]=arr[i];
        arr[i]=temp;
    }


}
